public class 最大回文数字 {

    public String largestPalindromic(String num) {
        int[] arr = new int[10];
        int n = num.length();
        StringBuilder sb = new StringBuilder();
        // 先算出所有的数字,统计一下个数
        for (int i = 0; i < n; i++) {
            int ch = num.charAt(i) - '0';
            arr[ch]++;
        }
        // 如果都是 0,直接返回 0
        if (arr[0] == n) return "0";
        // 如果个数大于 2,就加入到 sb 中,后续再使用反转
        for (int i = 9; i >= 0; i--) {
            if (arr[i] > 1) {
                int x = arr[i] / 2;
                int y = arr[i] % 2;
                while (x-- > 0) {
                    sb.append(i);
                }
                arr[i] = y;
            }
        }
        String s1 = sb.toString(); // 左半边
        String s2 = sb.reverse().toString(); // 右半边
        String s3; // 中间的
        sb.setLength(0); // 复用 sb,来存储中间的数
        for (int i = 9; i >= 0; i--) {
            if (arr[i] == 1) {
                sb.append(i);
                break;
            }
        }
        s3 = sb.toString();
        String ans = s1 + s3 + s2;
        if (ans.charAt(0) == '0') return s3;
        return ans;
    }
}
